package com.hyb.algorithm.data.struct.backtrack;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 * 47. 全排列 II
 * https://leetcode.cn/problems/permutations-ii/description/
 *
 * @author: ybhu
 * @create: 2023/12/28 19:16
 */
public class PermuteUnique {


    private   List<List<Integer>> res;

    public List<List<Integer>> permuteUnique(int[] nums) {

        res=new ArrayList<List<Integer>>();
        boolean[] used=new boolean[nums.length];
        Set<String> set=new HashSet<String>();

        backTack(nums,0,new ArrayList<Integer>(),set,used);
        return res;
    }

    public void backTack(int[] nums,int count,List<Integer> list ,Set<String> set,boolean[] used){

        //递归终止条件
        if(count==nums.length){
            String key="";
            for(Integer s:list){
                key+=s+"-";
            }

            if(set.contains(key)){
                return;
            }
            //深度拷贝
            res.add(new ArrayList(list));
            set.add(key);

            return;
        }

        for(int i=0;i<nums.length;i++){
            if(!used[i]){
                list.add(nums[i]);
                used[i]=true;
                //回溯
                backTack(nums,count+1,list,set,used);
                used[i]=false;
                list.remove(list.size()-1);
            }
        }
    }
}
